package 回溯;

import java.util.ArrayList;
import java.util.List;

/**
 * 17. 电话号码的字母组合
 * 给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
 * 给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
 *
 *  问题分析
 * 题目要求根据输入的数字字符串（2-9），生成所有可能的字母组合，每个数字对应手机按键上的多个字母。
 * 例如，输入“23”应输出["ad","ae","af","bd","be","bf","cd","ce","cf"]。
 *
 * 核心思路
 * 使用回溯法（深度优先搜索）逐层生成所有可能的组合：
 *
     * 建立映射表：将数字与对应的字母字符串建立映射。
     * 递归生成组合：从第一个数字开始，遍历其所有可能的字母，依次拼接并递归处理下一个数字。
     * 终止条件：当处理完所有数字时，将当前组合加入结果列表。
 */
public class L_17 {

    public List<String> letterCombinations(String digits) {
        List<String> result = new ArrayList<>();
        if (digits == null || digits.isEmpty()) return result;

        // 数字到字母的映射表
        String[] mapping = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
        backtrack(result, new StringBuilder(), digits, 0, mapping);
        return result;
    }

    /**
     *
     * @param result 结果值
     * @param current 当前组合
     * @param digits 当前输入字符串
     * @param index 递归索引
     * @param mapping 数字到字母的映射表
     */
    private void backtrack(List<String> result, StringBuilder current, String digits, int index, String[] mapping){
        // 终止条件：已经处理完了所有数字，index = digits.length()
        if(index == digits.length()){
            result.add(current.toString());
            return;
        }
        // 获取当前输入字符窜对应的字母组合
        char digit = digits.charAt(index);
        String letter = mapping[digit - '0'];

        // 遍历每个字母，递归生成所有组合
        for (char c : letter.toCharArray()){
            // 当前组合拼接字符
            current.append(c);
            backtrack(result,current, digits, index + 1, mapping); // 继续处理下一个数字
            current.deleteCharAt(current.length() - 1); // 进行回溯，删除当前拼接的字符，不影响下一次递归
        }
    }
}
